package com.eddie.tree.threadedbinarytree;

import lombok.Setter;


/**
 * 创建ThreadedBinaryTree 实现了线索化功能的二叉树
 */
class ThreadedBinaryTree {
    @Setter
    private HeroNode root;

    /**
     * 为了实现线索化，需要创建一个指向当前节点的前驱节点的指针
     * 在递归进行线索化时，pre总是保留前一个节点
     */
    private HeroNode pre = null;

    /**
     * 遍历线索化二叉树的方法
     */
    public void threadedList() {
        if (pre == null) {
            return;
        }

        HeroNode node = root;
        while (node != null) {
            //循环找到leftType=1的节点，第一个找到的应该是8节点
            //后面随着遍历而变化，因为当leftType=1的时候说明该节点按照线索化处理后的有效节点
            while (node.getLeftType() == TypeConstant.TREE_TYPE) {
                //第一个找到8
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node.getRightType() == TypeConstant.THREAD_TYPE) {
                //获取当前节点的后继节点
                node = node.getRight();
                System.out.println(node);
            }
            //替换遍历的节点
            node = node.getRight();
        }
    }

    public void preThreadedList() {
        if (pre == null) {
            return;
        }

        HeroNode node = root;
        while (node != null) {
            //打印当前节点
            System.out.println(node);
            //循环找到leftType=1的节点，第一个找到的应该是8节点
            //后面随着遍历而变化，因为当leftType=1的时候说明该节点按照线索化处理后的有效节点
            while (node.getLeftType() == TypeConstant.TREE_TYPE) {
                //第一个找到8
                node = node.getLeft();
                System.out.println(node);
            }

            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node.getRightType() == TypeConstant.THREAD_TYPE) {
                //获取当前节点的后继节点
                node = node.getRight();
                System.out.println(node);
            }
            //替换遍历的节点
            node = node.getRight();
        }
    }

    /**
     * 重载线索化方法
     */
    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 编写对二叉树定义中序线索化的方法
     *
     * @param node 就是当前需要线索化的节点
     */
    public void threadedNodes(HeroNode node) {
        //如果node等于null就不能线索化
        if (node == null) {
            return;
        }

        //按照中序线索化的方法
        /*
        1、先线索化左子树
        2、线索化当前节点
        3、在线索化右子树
         */
        //一
        threadedNodes(node.getLeft());

        //二
        /*
        1、处理当前节点的前驱节点
           以8来理解
           8节点的left指向null；leftType =1
         */
        if (node.getLeft() == null) {
            //当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(TypeConstant.THREAD_TYPE);
        }

        //处理pre后继节点，pre是保留过的上一个节点，
        //如果上一个节点的右指针为空表示没有后继节点并且没有右子节点或右子树,在这种条件下再去将pre的右节点设置为当前的节点
        // ，当前节点相当于线索存入到pre中
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(TypeConstant.THREAD_TYPE);
        }

        //！！！ 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;

        //三
        threadedNodes(node.getRight());
    }

    //前序遍历
    public void preOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.preOrder();
    }

    /**
     * //中序遍历
     */
    public void infixOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.infixOrder();
    }

    //后续遍历
    public void postOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.postOrder();
    }

    public void infixOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.infixOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void postOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.postOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void preOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.preOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void delHeroNode(int id) {
        if (!isEmpty()) {
            if (root.getNo() == id) {
                root = null;
            } else {
                root.delHeroNode(id);
            }
        } else {
            System.out.println("树为空");
        }
    }

    boolean isEmpty() {
        return this.root == null;
    }
}

